package org.leetcode.easy;

import org.junit.Test;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
// 349. 两个数组的交集
public class Intersection {
    private int[] intersection(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        if (nums1.length <= nums2.length) {
            return binarySearchRun(nums1, nums2);
        } else {
            return binarySearchRun(nums2, nums1);
        }

    }

    private int[] binarySearchRun(int[] minNums, int[] maxNums) {
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < minNums.length; i++) {
            int j;
            if ((j = binarySearch(maxNums, minNums[i], 0, maxNums.length - 1)) >= 0) {
                set.add(j);
            }
        }
        int[] nums = new int[set.size()];
        for (int j = 0; j < set.size(); j++) {
            nums[j] = (int) set.toArray()[j];
        }
        return nums;
    }

    private int binarySearch(int[] nums, int target, int left, int right) {
        if (left > right) {
            return -1;
        }
        int mid = (left + right) / 2;
        if (nums[mid] > target) {
            return binarySearch(nums, target, left, mid - 1);
        } else if (nums[mid] < target) {
            return binarySearch(nums, target, mid + 1, right);
        }
        return nums[mid];
    }

    @Test
    public void test() {
        int[] nums1 = new int[]{8,0,3};
        int[] nums2 = new int[]{0,0};
        System.out.println(Arrays.toString(intersection(nums1, nums2)));
    }
}
